<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN"
            "http://www.w3.org/TR/REC-html40/loose.dtd">
<HTML>
<HEAD>



<META http-equiv="Content-Type" content="text/html; charset=ISO-8859-1">
<META name="GENERATOR" content="hevea 1.08">
<LINK rel="stylesheet" type="text/css" href="tutorial.css">
<TITLE>
A Simple Example
</TITLE>
</HEAD>
<BODY >
<A HREF="tutorial123.html"><IMG SRC ="previous_motif.gif" ALT="Previous"></A>
<A HREF="tutorial121.html"><IMG SRC ="contents_motif.gif" ALT="Up"></A>
<A HREF="tutorial125.html"><IMG SRC ="next_motif.gif" ALT="Next"></A>
<HR>

<H2 CLASS="section"><A NAME="htoc241">17.3</A>&nbsp;&nbsp;A Simple Example</H2><UL>
<LI><A HREF="tutorial124.html#toc119">Problem Definition</A>
<LI><A HREF="tutorial124.html#toc120">Program to Determine Satisfiability</A>
<LI><A HREF="tutorial124.html#toc121">Program Performing Optimisation</A>
</UL>

<A NAME="toc119"></A>
<H3 CLASS="subsection"><A NAME="htoc242">17.3.1</A>&nbsp;&nbsp;Problem Definition</H3>
We start with a simple example of linear constraints being posted to
<TT>eplex</TT> and the other constraints being sent to <TT>ic</TT>.<BR>
<BR>
The example problem involves three tasks (<EM>task1, task2, task3</EM>)
and a time point 
<EM>time1</EM>. We enforce the following constraints:
<UL CLASS="itemize"><LI CLASS="li-itemize">
Exactly one of <EM>task1</EM> and <EM>task2</EM> overlaps with <EM>time1</EM>
<LI CLASS="li-itemize">Both tasks <EM>task1</EM> and <EM>task2</EM> precede <EM>task3</EM>
</UL>
<A NAME="toc120"></A>
<H3 CLASS="subsection"><A NAME="htoc243">17.3.2</A>&nbsp;&nbsp;Program to Determine Satisfiability</H3>
For this example we handle the first constraint using <TT>ic</TT>,
because it is not expressible as a conjunction of linear constraints,
and we handle the second pair of linear constraints using <TT>eplex</TT>.<BR>
<BR>

<TABLE CELLPADDING=10>
<TR><TD BGCOLOR="#CCFFCC">
<DL CLASS="description" COMPACT=compact><DT CLASS="dt-description">
<B>&otimes;</B><DD CLASS="dd-description"> Note that since we use both solvers <TT>eplex</TT> and <TT>ic</TT> we
will explicitly module qualify all numeric constraints to avoid
ambiguity.
</DL>
</TD>
</TR></TABLE>
<BR>
<A NAME="@default422"></A>
Each task has a start time <I>Start</I> and a duration <I>Duration</I>. 
We encode the (non-linear) overlap constraint in <TT>ic</TT> thus:

	<TABLE CELLPADDING=10>
<TR><TD BGCOLOR="#CCCCFF">
	<BLOCKQUOTE CLASS="quote"><PRE>
:- lib(ic).
overlap(Start,Duration,Time,Bool) :-
        % Bool is 1 if the task with start time Start and duration
        % Duration overlaps time point Time and 0 otherwise
       ic: (Bool #= ((Time $&gt;= Start) and (Time $=&lt; Start+Duration-1))).
</PRE></BLOCKQUOTE></TD>
</TR></TABLE>
The variable <EM>Bool</EM> takes the value 1 if the task overlaps the
time point, and 0 otherwise. To enforce that only one task overlaps
the time point, the associated boolean variables must sum to 1.<BR>
<BR>
<A NAME="@default423"></A>
We encode the (linear) precedence constraint in <TT>eplex</TT> thus:

	<TABLE CELLPADDING=10>
<TR><TD BGCOLOR="#CCCCFF">
	<BLOCKQUOTE CLASS="quote"><PRE>
:- lib(eplex).
before(Start,Duration,Time) :-
        % the task with start time Start and duration Duration is
        % completed before time point Time
        eplex: (Start+Duration $=&lt; Time).
</PRE></BLOCKQUOTE></TD>
</TR></TABLE><BR>
To complete the program, we can give durations of 3 and 5 to <EM>task1</EM> and <EM>task2</EM>, and have the linear solver minimise the start
time of <EM>task3</EM>:

	<TABLE CELLPADDING=10>
<TR><TD BGCOLOR="#CCCCFF">
	<BLOCKQUOTE CLASS="quote"><PRE>
ic_constraints(Time,S1,S2,B1,B2) :-
        % exactly one of task 1 with duration 3 and task 2 with
        % duration 5 overlaps time point Time
        ic: ([S1,S2]::1..20),
        overlap(S1,3,Time,B1),
        overlap(S2,5,Time,B2),
        ic: (B1+B2 #= 1).

eplex_constraints(S1,S2,S3) :-
        % task 1 with duration 3 and task 2 with duration 5 are both
        % completed before the start time of task 3
        before(S1,3,S3),
        before(S2,5,S3).
 
hybrid1(Time, [S1,S2,S3], End) :-
        % give the eplex cost variable some default bounds
        ic:(End $:: -1.0Inf..1.0Inf),
        % we must give the start time of task 3 ic bounds in order to
        % suspend on changes to them
        ic: (S3::1..20),
        % setup the problem constraints
        ic_constraints(Time,S1,S2,B1,B2),
        % setup the eplex solver
        eplex_constraints(S1,S2,S3),
        eplex:eplex_solver_setup(min(S3),End,[sync_bounds(yes)],[ic:min,ic:max]),
        % label the variables occurring in ic constraints
        labeling([B1,B2,S1,S2]).

</PRE></BLOCKQUOTE></TD>
</TR></TABLE>
During the labeling of the boolean variables, the bounds on <I>S</I>1 and
<I>S</I>2 are tightened as a result of <TT>ic</TT> propagation, which wakes
the linear solver, which has been set to trigger on ic bound changes (<TT>ic:min, ic:max</TT>). Note that all variables occurring in the linear
solver must then have ic attributes.<BR>
<BR>
The ic bounds are passed to the linear solver before
the problem is solved with the option <TT>sync_bounds(yes)</TT>. The
linear solver derives a new lower bound for <I>End</I>. In case this
exceeds its upper bound, the search fails and backtracks.<BR>
<BR>
Using this method of bound communication the bounds for <EM>all</EM>
problem variables are retrieved from any bounds solvers before
resolving the linear problem. If however only a small number of variable
bounds have changed sufficiently to affect the relaxed solution
this will be inefficient.<BR>
<BR>
Instead bound updates for individual variables and bound solvers may
be transferred to the linear solver separately. This may be achieved
(using the <TT>eplex</TT> instance's <TT>::/2</TT>) either explicitly within
the search code or through demons attached to the appropriate solver
bound changes. <BR>
<BR>
Note that the optimisation performed by the linear
solver does not respect the <TT>ic</TT> constraints, so a correct answer
can only be guaranteed once all the variables involved in <TT>ic</TT>
constraints are instantiated.<BR>
<BR>
Henceforth we will not explicitly show the loading of the <TT>ic</TT> and
<TT>eplex</TT> libraries.<BR>
<BR>
<A NAME="toc121"></A>
<H3 CLASS="subsection"><A NAME="htoc244">17.3.3</A>&nbsp;&nbsp;Program Performing Optimisation</H3>
<A NAME="@default424"></A>
When different constraints are sent to <TT>ic</TT> and to <TT>eplex</TT>,
the optimisation built into the linear solver must be combined with
the optimisation provided by the ECL<SUP><I>i</I></SUP>PS<SUP><I>e</I></SUP> <EM>branch_and_bound</EM>
library. <BR>
<BR>
The following program illustrates how to combine these optimisations:

	<TABLE CELLPADDING=10>
<TR><TD BGCOLOR="#CCCCFF">
	<BLOCKQUOTE CLASS="quote"><PRE>
:- lib(branch_and_bound).

hybrid2(Time, [S1,S2,S3], End) :-
        % give the eplex cost variable some default bounds
        ic:(End $:: -1.0Inf..1.0Inf),
        % we must give the start time of task 3 ic bounds in order to
        % suspend on changes to them
        ic: (S3::1..20),
        % setup the problem constraints
        ic_constraints(Time,S1,S2,B1,B2),
        eplex_constraints(S1,S2,S3),
        % perform the optimisation
        both_opt(labeling([B1,B2,S1,S2]),min(S3),End).

both_opt(Search,Obj,Cost) :-
        % setup the eplex solver
        eplex:eplex_solver_setup(Obj,Cost,[sync_bounds(yes)],[ic:min,ic:max]),
        % minimize Cost by branch-and-bound
        minimize((Search,eplex_get(cost,Cost)),Cost).
</PRE></BLOCKQUOTE></TD>
</TR></TABLE><BR>

	<BLOCKQUOTE CLASS="figure"><DIV CLASS="center"><HR WIDTH="80%" SIZE=2></DIV>
	<DIV CLASS="center">
	<TABLE CELLPADDING=10>
<TR><TD BGCOLOR="#DB9370">
	
A simple way to combine <TT>eplex</TT> and <TT>ic</TT> is to send the linear
constraints to <TT>eplex</TT> and the other constraints to <TT>ic</TT>.
The optimisation primitives must also be combined.

	</TD>
</TR></TABLE>
	</DIV>
	<BR>
<BR>
<DIV CLASS="center">Figure 17.2: A Simple Example</DIV><BR>
<BR>

	<DIV CLASS="center"><HR WIDTH="80%" SIZE=2></DIV></BLOCKQUOTE>
<HR>
<A HREF="tutorial123.html"><IMG SRC ="previous_motif.gif" ALT="Previous"></A>
<A HREF="tutorial121.html"><IMG SRC ="contents_motif.gif" ALT="Up"></A>
<A HREF="tutorial125.html"><IMG SRC ="next_motif.gif" ALT="Next"></A>
</BODY>
</HTML>
